package com.cat.dynamicPlanning02;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/count-square-submatrices-with-all-ones/description/?envType=problem-list-v2&envId=dynamic-programming
 * @create 2025/11/6 15:16
 * @since JDK17
 */

public class Solution48 {
    int sum(int[][]mat, int a, int b, int c, int d) {
        return mat[c][d] - mat[a - 1][d] - mat[c][b - 1] + mat[a - 1][b - 1];
    }
    public int countSquares(int[][] matrix) {
        int n = matrix.length, m = matrix[0].length, ans = 0;
        int[][] mat = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                mat[i + 1][j + 1] = matrix[i][j];
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                mat[i][j] += mat[i - 1][j] + mat[i][j - 1] - mat[i - 1][j - 1];
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                for (int k = 0; k <= Math.min(n - i, m - j); k++) {
                    if ((k + 1) * (k + 1) == sum(mat, i, j, i + k, j + k)) {
                        ans++;
                    }
                }
            }
        }

        return ans;
    }
}
